#include <iostream>
#include <fstream>
#include <string>
#include <list>
#include <vector>
#include <set>
#include <map>
#include <climits>

using namespace std;

enum eColor {
    E_BLACK,
    E_WHITE
};

void dfsVisit(int root, vector<list<int>>& mst, vector<int>& pi, vector<eColor>& color) {
    color[root]=E_BLACK;
    list<int>::iterator iEnd = mst[root].end();
    for (list<int>::iterator i=mst[root].begin(); i!=iEnd; ++i) {
        if (color[*i]==E_WHITE) {
            pi[*i]=root;
            dfsVisit(*i, mst, pi, color);
        }
    }
}

void dfs(int root, vector<list<int>>& mst, vector<int>& pi) {
    int n=mst.size();
    vector<eColor> color(n, E_WHITE);
    pi.resize(n, 0);
    pi[root]=-1;
    dfsVisit(root, mst, pi, color);
    for (int i=0; i<n; ++i) {
        if (color[i]==E_WHITE) {
            dfsVisit(i, mst, pi, color);
        }
    }
}

void prima(vector<vector<double>>& adjMatrix, vector<list<int>>& mst) {
    int n=adjMatrix.size();
    vector<double> key(n, numeric_limits<double>::max());
    vector<int> pi(n, -1);
    multimap<double, int> q;
    set<int> closed;

    mst.resize(0);
    mst.resize(n);

    key[0]=0;
    q.insert(make_pair(key[0], 0));

    while (!q.empty()) {
        int currentVertex=q.begin()->second;
        q.erase(q.begin());
        closed.insert(currentVertex);

        for (size_t i=0; i<n; ++i) {
            if ((adjMatrix[currentVertex][i] != 0)
                && (closed.find(i) == closed.end())
                && (adjMatrix[currentVertex][i] < key[i])) {
                    pi[i]=currentVertex;
                    key[i]=adjMatrix[currentVertex][i];
                    for (multimap<double, int>::iterator m=q.lower_bound(key[i]); m!=q.upper_bound(key[i]); ++m) {
                        if (m->second == i) {
                            q.erase(m);
                            break;
                        }
                    }
                    q.insert(make_pair(key[i], i));
            }
        }
    }

    for (size_t i=0; i<pi.size(); ++i) {
        if (pi[i] > -1) {
            mst[i].push_back(pi[i]);
            mst[pi[i]].push_back(i);
        }
    }
}

void printMst(vector<list<int> >& mst) {
	cout<<endl<<"MST:"<<endl;
	for (size_t j = 0; j < mst.size(); ++j) {
		for (list<int>::iterator i=mst[j].begin(); i!=mst[j].end(); ++i) {
			if (j < *i) {
				cout<<j<<" - "<<*i<<endl;
			}
		}
	}
	cout<<endl;
}

void subMstFinder(int root, vector<list<int>>& mst, vector<bool>& isInSubMst) {
    int n=mst.size();
    isInSubMst[root]=true;

    list<int>::iterator iMstEnd=mst[root].end();
    for(list<int>::iterator i=mst[root].begin(); i!=iMstEnd; ++i) {
        if(!isInSubMst[*i]) {
            subMstFinder(*i, mst, isInSubMst);
        }
    }
}

void addEdge(vector<vector<double> >& adjMatrix, vector<list<int> >& mst, int start, int end, int weight) {
    int n=adjMatrix.size();

    if(adjMatrix[start][end] > 0) {
        cout<<"Error: this edge has already existed";
    } else {
        adjMatrix[start][end]=adjMatrix[end][start]=weight;
        vector<int> pi;
        dfs(end, mst, pi);
        double maxWeight=weight;
        int biggestStart=start;
        int biggestEnd=end;
        for (size_t i=end; pi[i]!=-1; i=pi[i]) {
            if (adjMatrix[i][pi[i]] > maxWeight) {
                maxWeight=adjMatrix[i][pi[i]];
                biggestStart=i;
                biggestEnd=pi[i];
            }
        }
        if (!(biggestStart==start && biggestEnd==end)) {
            mst[end].push_back(start);
            mst[start].push_back(end);
            list<int>::iterator iStartListEnd = mst[biggestStart].end();
            list<int>::iterator iEndListEnd = mst[biggestEnd].end();
            for (list<int>::iterator i=mst[biggestStart].begin(); i!=iStartListEnd; ++i) {
                if (*i == biggestEnd) {
                    mst[biggestStart].erase(i);
                    break;
                }
            }
            for (list<int>::iterator i=mst[biggestEnd].begin(); i!=iEndListEnd; ++i) {
                if (*i == biggestStart) {
                    mst[biggestEnd].erase(i);
                    break;
                }
            }
        }
    }
}

void removeEdge(vector<vector<double>>& adjMatrix, vector<list<int>>& mst, int start, int end) {
    int n=adjMatrix.size();

    if (adjMatrix[start][end] == 0) {
		cout<<"Error: this edge hasn't existed"<<endl;
	} else {
        adjMatrix[start][end]=adjMatrix[end][start]=0;
        list<int>::iterator iMstEnd=mst[start].end();
        bool isInMst=false;
        for (list<int>::iterator i=mst[start].begin(); i!=iMstEnd; ++i) {
            if (*i == end) {
                mst[start].erase(i);
                list<int>::iterator riMstEnd=mst[end].end();
                for (i=mst[end].begin(); i!=riMstEnd; ++i) {
                    if (*i == start) {
                        mst[end].erase(i);
                        break;
                    }
                }
                isInMst=true;
                break;
            }
        }
        if (isInMst) {
            vector<bool> isInFirstMst;
            int n=mst.size();
            isInFirstMst.resize(n, false);
            subMstFinder(0, mst, isInFirstMst);

            double min = numeric_limits<double>::infinity();
            int minStart=numeric_limits<double>::min();
            int minEnd=numeric_limits<double>::min();
            int amSize=adjMatrix.size();
            for (size_t i=0; i<amSize; ++i) {
                for (size_t j=0; j<amSize; ++j) {
                    if(isInFirstMst[i] && !isInFirstMst[j] && adjMatrix[i][j]>0 && adjMatrix[i][j]<min) {
                        min=adjMatrix[i][j];
                        minStart=i;
                        minEnd=j;
                    }
                }
            }
            if (minStart==-1) {
                cout<<"Graph is broken!"<<endl;

                return;
            } else {
                mst[minStart].push_back(minEnd);
                mst[minEnd].push_back(minStart);
            }
        }
    }
}

void commandExecutor(vector<vector<double>>& adjMatrix, vector<list<int >>& mst) {
	while (true) {
		string cmd;
		cin>>cmd;
        if(cmd=="exit") {
            return;
        } else {
            if (cmd=="add") {
                int start, end, weight;
                cin>>start>>end>>weight;
                addEdge(adjMatrix, mst, start, end, weight);
                printMst(mst);
            } else {
                if (cmd=="rmv") {
                    int start, end;
                    cin>>start>>end;
                    removeEdge(adjMatrix, mst, start, end);
                    printMst(mst);
                } else {
                    cout<<"Error: invalid command '"<<cmd<<"'"<<endl;
                    return;
                }
            }
        }
	}
}

int main() {
    if(freopen("in.txt", "r", stdin)==NULL) {
        cout<<"Error: input file can't be opened";
        return 1;
    }

    if(freopen("out.txt", "w", stdout)==NULL) {
        cout<<"Error: output file can't be opened";
        return 1;
    }

    int countOfVertices, countOfEdges;
    vector<vector<double>> adjMatrix;

    cin>>countOfVertices;
    cin>>countOfEdges;
    adjMatrix.resize(countOfVertices);
    for (int i=0; i<countOfVertices; ++i) {
        adjMatrix[i].resize(countOfVertices);
     }

     for (int i=0; i<countOfEdges; ++i) {
         int x, y;
         cin>>x>>y;
         cin>>adjMatrix[x][y];
         adjMatrix[y][x]=adjMatrix[x][y];
     }
    
    vector<list<int>> mst;
    prima(adjMatrix, mst);

    printMst(mst);

    commandExecutor(adjMatrix, mst);

    return 0;
}